package main

import (
	"log"

	"gitee.com/smiecj/mygocodeproject/dp"
)

func main() {
	/*height := []int {1,8,6,2,5,4,8,3,7}
	maxVolume := dp.MaxArea(height)
	fmt.Println(maxVolume)*/

	/*nums := []int{1, 1, 2, 3}
	retArr := dfs.PermuteUnique(nums)
	for index, currentNumArr := range retArr {
		log.Printf("当前第%d个数组: %v", index, currentNumArr)
	}*/

	// 1 6 9 14 16 70
	//nums := []int{-55, -24, -18, -11, -7, -3, 4, 5, 6, 9, 11, 23, 33}
	//target := 0
	//fmt.Println(dfs.ThreeSumClosest(nums, target))

	/*islandMark := [][]byte {
		{1, 1, 1, 1, 0},
		{1, 1, 0, 1, 0},
		{1, 1, 0, 0, 0},
		{0, 0, 0, 0, 0},
	}*/
	/*islandMark := [][]byte{
		{1, 1, 1, 0},
		{1, 1, 1, 0},
		{1, 0, 0, 0},
		{1, 1, 0, 0},
		{0, 0, 0, 0},
	}
	fmt.Println(dfs.NumIslands(islandMark))*/

	// n = 3: 011 1 001
	/*fmt.Println(recursion.FindKthBit(3, 1))
	fmt.Println(recursion.FindKthBit(3, 2))
	fmt.Println(recursion.FindKthBit(3, 3))
	fmt.Println(recursion.FindKthBit(3, 4))
	fmt.Println(recursion.FindKthBit(3, 5))
	fmt.Println(recursion.FindKthBit(3, 6))
	fmt.Println(recursion.FindKthBit(3, 7))*/

	/*fmt.Println(recursion.FindKthBit(4, 11))
	fmt.Println(recursion.FindKthBit(1, 1))
	fmt.Println(recursion.FindKthBit(2, 3))
	fmt.Println(recursion.FindKthBit(3, 1))*/

	//fmt.Println(number.MinOperations(3))
	//fmt.Println(number.MinOperations(4))
	//fmt.Println(number.MinOperations(5))
	//fmt.Println(number.MinOperations(6))
	//fmt.Println(number.MinOperations(7))
	//fmt.Println(number.MinOperations(8))

	//posArr := []int{1,2,3,4,7}
	//ballNum := 3
	/* posArr := []int{5, 4, 3, 2, 1, 100000000}
	ballNum := 2
	log.Println(binary.MaxDistance(posArr, ballNum))

	totalPointNum := 2
	prerequisites := [][]int{
		{1, 0}, {2, 0}, {2, 1}, {3, 1}, {3, 2}, {4, 2}, {4, 3}, {5, 3}, {5, 4}, {6, 4}, {6, 5}, {7, 5}, {7, 6}, {8, 6}, {8, 7}, {9, 7}, {9, 8}, {10, 8}, {10, 9}, {11, 9}, {11, 10}, {12, 10}, {12, 11}, {13, 11}, {13, 12}, {14, 12}, {14, 13}, {15, 13}, {15, 14}, {16, 14}, {16, 15}, {17, 15}, {17, 16}, {18, 16}, {18, 17}, {19, 17}, {19, 18}, {20, 18}, {20, 19}, {21, 19}, {21, 20}, {22, 20}, {22, 21}, {23, 21}, {23, 22}, {24, 22}, {24, 23}, {25, 23}, {25, 24}, {26, 24}, {26, 25}, {27, 25}, {27, 26}, {28, 26}, {28, 27}, {29, 27}, {29, 28}, {30, 28}, {30, 29}, {31, 29}, {31, 30}, {32, 30}, {32, 31}, {33, 31}, {33, 32}, {34, 32}, {34, 33}, {35, 33}, {35, 34}, {36, 34}, {36, 35}, {37, 35}, {37, 36}, {38, 36}, {38, 37}, {39, 37}, {39, 38}, {40, 38}, {40, 39}, {41, 39}, {41, 40}, {42, 40}, {42, 41}, {43, 41}, {43, 42}, {44, 42}, {44, 43}, {45, 43}, {45, 44}, {46, 44}, {46, 45}, {47, 45}, {47, 46}, {48, 46}, {48, 47}, {49, 47}, {49, 48}, {50, 48}, {50, 49}, {51, 49}, {51, 50}, {52, 50}, {52, 51}, {53, 51}, {53, 52}, {54, 52}, {54, 53}, {55, 53}, {55, 54}, {56, 54}, {56, 55}, {57, 55}, {57, 56}, {58, 56}, {58, 57}, {59, 57}, {59, 58}, {60, 58}, {60, 59}, {61, 59}, {61, 60}, {62, 60}, {62, 61}, {63, 61}, {63, 62}, {64, 62}, {64, 63}, {65, 63}, {65, 64}, {66, 64}, {66, 65}, {67, 65}, {67, 66}, {68, 66}, {68, 67}, {69, 67}, {69, 68}, {70, 68}, {70, 69}, {71, 69}, {71, 70}, {72, 70}, {72, 71}, {73, 71}, {73, 72}, {74, 72}, {74, 73}, {75, 73}, {75, 74}, {76, 74}, {76, 75}, {77, 75}, {77, 76}, {78, 76}, {78, 77}, {79, 77}, {79, 78}, {80, 78}, {80, 79}, {81, 79}, {81, 80}, {82, 80}, {82, 81}, {83, 81}, {83, 82}, {84, 82}, {84, 83}, {85, 83}, {85, 84}, {86, 84}, {86, 85}, {87, 85}, {87, 86}, {88, 86}, {88, 87}, {89, 87}, {89, 88}, {90, 88}, {90, 89}, {91, 89}, {91, 90}, {92, 90}, {92, 91}, {93, 91}, {93, 92}, {94, 92}, {94, 93}, {95, 93}, {95, 94}, {96, 94}, {96, 95}, {97, 95}, {97, 96}, {98, 96}, {98, 97}, {99, 97},
	}
	log.Println(dp.CanFinish(totalPointNum, prerequisites)) */

	// trim
	/*trim := tree.Constructor()
	trim.Insert("apple")
	log.Println(trim.Search("app"))
	log.Println(trim.StartsWith("app"))
	trim.Insert("app")
	log.Println(trim.Search("app"))*/

	/*log.Println(simple.IsIsomorphic("egg", "add"))
	log.Println(simple.IsIsomorphic("paper", "title"))
	log.Println(simple.IsIsomorphic("foo", "bar"))*/

	// log.Println(simple.CountPrimes(2))

	/*log.Println(binary.RangeBitwiseAnd(5, 7))
	log.Println(binary.RangeBitwiseAnd(0, 1))
	log.Println(binary.RangeBitwiseAnd(7, 8))*/

	//log.Println(greedy.MinSubArrayLen(7, []int{2, 3, 1, 2, 4, 3}))

	/*log.Println(dfs.FindOrder(3, [][]int{
		{0, 1},
		{0, 2},
		{1, 2},
	}))*/

	//log.Println(simple.IsValid("()[]{}"))
	//log.Println(simple.IsValid("()"))
	//log.Println(simple.IsValid("([)]"))

	//log.Println(bfs.MinSwapsCouples([]int{0, 2, 1, 3}))
	//log.Println(bfs.MinSwapsCouples([]int{3, 2, 0, 1}))
	//log.Println(bfs.MinSwapsCouples([]int{0, 2, 3, 4, 1, 5}))
	//log.Println(bfs.MinSwapsCouples([]int{6,2,1,7,4,5,3,8,0,9}))

	//simple.RemoveDuplicates([]int{0, 0, 1, 1, 1, 2})

	//log.Println(recursion.GenerateParenthesis(3))
	//log.Println(recursion.GenerateParenthesis(10))

	//log.Println(array.ThreeSum([]int{-1,0,1,2,-1,-4}))
	//log.Println(greedy.MinKBitFlips([]int{0, 0, 1, 1}, 2))
	//log.Println(greedy.MinKBitFlips([]int{1, 0, 1}, 2))
	//log.Println(greedy.MinKBitFlips([]int{0,0,0,1,0,1,1,0}, 3))

	//log.Println(array.LongestOnes([]int{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 2))
	//log.Println(array.LongestOnes([]int{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 3))
	//log.Println(array.LongestOnes([]int{0, 0, 1, 1, 1, 0}, 0))

	//log.Println(simple.Transpose([][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}))

	//log.Println(simple.MaxProfit([]int{7,1,5,3,6,4}))
	//log.Println(simple.MaxProfit([]int{1,2,3,4,5}))
	//log.Println(simple.MaxProfit([]int{7,6,4,3,1}))

	//toRotateArr := []int{1,2,3,4,5,6,7}
	//toRotateArr := []int{-1,-100,3,99}
	//toRotateArr := []int{1,2,3,4,5,6}
	//simple.Rotate(toRotateArr, 4)
	//log.Println(toRotateArr)

	//log.Println(dp.ClimbStairs(3))

	//log.Println(dp.FindGreatestSumOfSubArray([]int{1, -2, 3, 10, -4, 7, 2, -5}))

	//log.Println(simple.MaxProfitOnce([]int{7,6,4,3,1}))
	//log.Println(simple.MaxProfitOnce([]int{7,1,5,3,6,4}))

	//log.Println(array.ContainsDuplicate([]int{1,2,3,1}))

	//log.Println(dp.Rob([]int{2,7,9,3,1}))

	//arr1 := []int{2, 0}
	//arr2 := []int{1}
	//array.Merge(arr1, 1, arr2, 1)
	//log.Println(arr1)

	//log.Println(array.PlusOne([]int{9,9,9}))

	//arr := []int{0, 1, 2, 0, 12, 5}
	//array.MoveZeroes(arr)
	//log.Println(arr)

	//log.Println(search.FirstBadVersion(10))

	//root := tree.NewTreeNode([]string{"1", "2", "2", "3", "4", "4", "3"})
	//log.Println(tree.IsSymmetric(root))

	//arr := [][]int{
	//	{1,2,3},
	//	{4,5,6},
	//	{7,8,9},
	//}
	//arr := [][]int{
	//	{5, 1, 9, 11},
	//	{2, 4, 8, 10},
	//	{13, 3, 6, 7},
	//	{15, 14, 12, 16},
	//}
	//array.Rotate(arr)
	//log.Println(arr)

	//timer := time.NewTimer(10 * time.Second)

	//log.Println(string2.IsPalindrome("0P"))

	//log.Println(string2.CountAndSay(2))
	//log.Println(string2.CountAndSay(3))
	//log.Println(string2.CountAndSay(4))
	//log.Println(string2.CountAndSay(5))
	//log.Println(string2.CountAndSay(6))
	//log.Println(string2.CountAndSay(30))

	// 测试append
	//slice := make([]int, 1)
	//slice = append(slice, 2)
	//append(slice, 2)
	//log.Println(slice)

	//head := nodelist.NewListNode([]int{1, 2, 3, 4, 5, 6})
	//head = nodelist.RemoveNthFromEnd(head, 2)
	//nodelist.PrintListNode(head)

	//l1 := nodelist.NewListNode([]int{1,3,5})
	//l2 := nodelist.NewListNode([]int{2,4,8})
	//mergeList := nodelist.MergeTwoLists(l1, l2)
	//nodelist.PrintListNode(mergeList)

	//log.Println(nodelist.IsPalindrome(nodelist.NewListNode([]int{1, 2, 3, 3, 2, 1})))
	//log.Println(nodelist.IsPalindrome(nodelist.NewListNode([]int{1, 2, 3, 5, 2, 1})))
	//log.Println(nodelist.IsPalindrome(nodelist.NewListNode([]int{1, 2, 3, 2, 1})))
	//log.Println(nodelist.IsPalindrome(nodelist.NewListNode([]int{1})))

	//s := solution.ArrConstructor([]int{1, 2, 3, 4})
	//log.Println(s.Shuffle())
	//log.Println(s.Shuffle())
	//log.Println(s.Shuffle())
	//log.Println(s.Reset())

	//log.Println(string2.LongestPalindrome("aacabdkacaa"))

	//log.Println(number.IncreasingTriplet([]int{1, 2, 3, 4, 5}))
	//log.Println(number.IncreasingTriplet([]int{20, 100, 10, 12, 5, 13}))
	//log.Println(number.IncreasingTriplet([]int{1, 2, 1, 2, 1, 2, 1, 2, 1, 2}))
	//log.Println(number.IncreasingTriplet([]int{1, 5, 0, 4, 1, 3}))
	//log.Println(number.IncreasingTriplet([]int{1, 1, -2, 6}))

	// tree.BuildTree([]int{3, 9, 20, 15, 7}, []int{9, 3, 15, 20, 7})
	// tree.BuildTree([]int{1, 2}, []int{1, 2})

	// nums := []int{1, 2, 3, 1}
	// hasSame := mappkg.ContainsDuplicate(nums)
	// fmt.Printf("has same: %v\n", hasSame)

	// arr := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	// fmt.Printf("max sub arr: %d\n", array.MaxSubArray(arr))

	// fmt.Printf("dp num = %d\n", dp.Fib(4))

	// slice := []int{2, 11, 7, 15}
	// fmt.Printf("Two num sum: %v\n", array.TwoSum(slice, 9))

	// nums1 := []int{1, 2, 3, 0, 0, 0}
	// nums2 := []int{2, 5, 6}
	// array.MergeWithTwoPointer(nums1, 3, nums2, 3)
	// fmt.Printf("merge two sort array: %v\n", nums1)

	// n := 4
	// fmt.Printf("tribonacci number %d: %d\n", n, dp.Tribonacci(n))

	// costArr := []int{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}
	// costArr := []int{10, 15, 20}
	// fmt.Printf("climb to top min cost: %d\n", dp.MinCostClimbingStairs(costArr))

	// log.Println(dp.MaxProfit([]int{7, 1, 5, 3, 6, 4}))
	// log.Println(dp.MaxProfit([]int{1, 2, 3, 4, 5}))
	// log.Println(dp.MaxProfit([]int{7, 6, 4, 3, 1}))

	// log.Println(dp.Rob2([]int{2, 3, 2}))
	// log.Println(dp.Rob2([]int{1, 2, 3, 1}))

	// log.Println(dp.DeleteAndEarn([]int{3, 4, 2}))
	// log.Println(dp.DeleteAndEarn([]int{2, 2, 3, 3, 3, 4}))
	// // expect: 18, actual: 24
	// log.Println(dp.DeleteAndEarn([]int{1, 1, 1, 2, 4, 5, 5, 5, 6}))
	// log.Println(dp.DeleteAndEarn([]int{1, 2, 3, 15, 16, 17, 18}))

	// log.Println(search.Binary([]int{-1, 0, 3, 5, 9, 12}, 9))
	// log.Println(search.Binary([]int{-1, 0, 3, 5, 9, 12}, 2))
	// log.Println(search.Binary([]int{2, 5}, 5))

	// log.Println(search.SearchInsert([]int{1, 3, 5, 6}, 5))
	// log.Println(search.SearchInsert([]int{1, 3, 5, 6}, 2))
	// log.Println(search.SearchInsert([]int{1, 3, 5, 6}, 7))
	// log.Println(search.SearchInsert([]int{1, 3, 5, 6}, 0))

	// log.Println(dp.CanJump([]int{2, 3, 1, 1, 4}))
	// log.Println(dp.CanJump([]int{3, 2, 1, 0, 4}))

	// log.Println(dp.JumpMinStep([]int{2, 3, 1, 1, 4}))
	// log.Println(dp.JumpMinStep([]int{2, 3, 0, 1, 4}))
	// log.Println(dp.JumpMinStep([]int{1, 2, 3}))
	// log.Println(dp.JumpMinStep([]int{3, 2, 1}))
	// log.Println(dp.JumpMinStep([]int{1, 1, 1, 1}))
	// log.Println(dp.JumpMinStep([]int{0}))
	// log.Println(dp.JumpMinStep([]int{4, 1, 1, 3, 1, 1, 1}))
	// log.Println(dp.JumpMinStep([]int{7, 0, 9, 6, 9, 6, 1, 7, 9, 0, 1, 2, 9, 0, 3}))

	// log.Println(dp.MaxProfitWithCoolDown([]int{1, 2, 3, 0, 2}))
	// log.Println(dp.MaxProfitWithCoolDown([]int{1, 2, 3, 4, 5, 0, 5, 6}))

	// tree.TestTree()
	// treeNode := tree.BuildTreeNode([]string{"3", "9", "20", "null", "null", "15", "7"})
	// levelOrderArr := tree.LevelOrder(treeNode)
	// log.Printf("tree level order: %v", levelOrderArr)

	// treeNode := tree.BuildTreeNode([]string{"1","2","3","null","5","null","4"})
	// rightSightArr := tree.RightSideView(treeNode)
	// log.Printf("tree right sight: %v", rightSightArr)

	/* myList := list.GetMyLinkedList()
	myList.AddAtHead(7)
	myList.AddAtHead(2)
	myList.AddAtHead(1) // 1 -> 2 -> 7
	myList.AddAtIndex(3, 0) // 1 -> 2 -> 7 -> 0
	myList.DeleteAtIndex(2) // 1 -> 2 -> 0
	myList.AddAtHead(6)
	myList.AddAtTail(4) // 6 -> 1 -> 2 -> 0 -> 4
	log.Printf("[list] current list: %s, len: %d", &myList, myList.Len())
	myList.Get(4)
	myList.AddAtHead(4)
	myList.AddAtIndex(5, 0)
	myList.AddAtHead(6) */

	// myList := list.GetMyLinkedList()
	// myList.AddAtIndex(0, 10)
	// myList.AddAtIndex(0, 20)
	// myList.AddAtIndex(1, 30) // 10 -> 30 -> 20
	// log.Printf("[list] current list: %s, len: %d", &myList, myList.Len())

	// node := tree.SortedArrayToBST([]int{-10,-3,0,5,9})
	// tree.PrintTreeNode(node)

	// node := tree.BuildTreeNode([]string{"3","9","20","null","null","15","7"})
	// retArr := tree.ZigzagLevelOrder(node)
	// for _, currentArr := range retArr {
	// 	log.Printf("%v", currentArr)
	// }

	// root := tree.BuildTreeNode([]string{"5","3","6","2","4","null","7"})
	// root = tree.DeleteNode(root, 3)
	// // root = tree.DeleteNode(root, 5)
	// tree.PrintTreeNode(root)

	/* lruCache := list.LRUCacheConstructor(2)
	lruCache.Put(2, 5)
	lruCache.Put(2, 6)
	log.Println(lruCache.Get(1)) // return -1
	log.Println(lruCache.Get(2)) // return 6
	lruCache.Put(1, 10)
	log.Println(lruCache.Get(1)) // return 10

	lruCache = list.LRUCacheConstructor(1)
	log.Println(lruCache.Get(6))
	log.Println(lruCache.Get(8))
	lruCache.Put(12, 1)
	log.Println(lruCache.Get(2))
	lruCache.Put(15, 11)
	lruCache.Put(5, 2)
	lruCache.Put(1, 15)
	lruCache.Put(4, 2)
	log.Println(lruCache.Get(5))
	lruCache.Put(15, 15) */

	// log.Println(array.Permute([]int{1, 2}))

	// log.Println(array.IncreasingTriplet([]int{1, 2, 3, 4, 5}))    // true
	// log.Println(array.IncreasingTriplet([]int{5, 4, 3, 2, 1}))    // false
	// log.Println(array.IncreasingTriplet([]int{2, 1, 5, 0, 4, 6})) // true
	log.Println(dp.IsOneBitCharacter([]int{1, 0, 0}))
	log.Println(dp.IsOneBitCharacter([]int{1, 1, 1, 0}))
	log.Println(dp.IsOneBitCharacter([]int{0, 0, 1, 0}))
}
